<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 8. Графы.Advanced</h2>
<ol>
  <li>Поиск паросочетания</li>
  <ol>
    <li>Кун = O(VE)</li>
    <li>Оптимизация: жадная инициализация</li>
    <li>Хопкрофт-Карп = алгоритм Диница для двудольного графа = O(EsqrtV) (с доказательством)</li>
  </ol></li>
  <li>Задачи на паросочетания</li>
  <ol>
    <li>Задача про такси (покрытие ацикличного графа путями)</li>
    <li>Теорема Дилворта и поиск максимальное антицепи</li>
    <li>Замощение грида доминошками</li>
    <li>Поиск минимального контролирующего множества в двудольном графе (оно же вершинное покрытие)</li>
    <li>Поиск максимального независимого множества в двудольном графе</li>
    <li>Покраска грида с дырками минимальным количество горизонтальных или вертикальных мазков.</li>
    <li>Максимальная двудольная антиклика (birthday)</li>
    <li>Доминирующее множество в первой доле (party)</li>
    <li>Есть m людей, каждый хочет улететь в момент времени с L<sub>i</sub> по R<sub>i</sub>, есть n самолетов, каждый улетает в момент времени x<sub>i</sub> и имеет вместимость k<sub>i</sub>.</li>
  </ol></li>
  <li>Покраски вершин графа</li>
  <ol>
    <li>Всегда можно в D + 1 цветов</li>
    <li>Теорема Брукса: если нет подграфа = K<sub>D+1</sub>, то можно в D цветов <a href="http://neerc.ifmo.ru/wiki/index.php?title.">Теорема Брукса</a></li>
    <li>Планарный граф всегда можно в 5 цветов (доказательство + алгоритм)</li>
    <li>Факт: планарный граф всегда можно в 4 цвета</li>
    <li>Неточные алгоритмы к задаче "раскрасить в min количество цветов"</li>
    <ol>
      <li>Идея1: min(V<sup>2</sup>, ElogV) [красим вершину, у которой min количество возможных вариантов, из таких случайную]</li>
      <li>Идея2: min(V<sup>2</sup>, ElogV) [удаляем из графа вершину минимальной степени, индукция]</li>
    </ol></li>
  </ol></li>
  <li>Покраска ребер графа</li>
  <ol>
    <li>Теорема Визинга: D &le; opt &le; D + 1 (в одну сторону очевидно, в другую нужно доказать)</li>
    <li>Конструктивное доказательство и алгоритм покраски в D + 1 цвет <a href="http://planetmath.org/proofofvizingstheoremforgraphs">(link)</a></li>
  </ol></li>
  <li>Покраска ребер двудольного графа</li>
  <ol>
    <li>Связь с паросочетаниями</li>
    <li>Лемма Холла, k-регулярный граф k-раскрашиваем.</li>
    <li>Покраска k-регулярного двудольного графа за O(k*Matching)</li>
    <li>Покраска произвольного двудольного графа</li>
    <li>Покраска 2<sup>k</sup>-регулярного графа за O(kE)</li>
    <li>Покраска k-регулярного графа за O(EsqrtV*logk)</li>
  </ol></li>
</ol>
